package cn.fansunion.leecode.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 697. 数组的度 给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
 * 
 * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/degree-of-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-2-26
 */
public class DegreeOfAnArray {
    /*示例 1：
    
    输入：nums = [1,2,2,3,1]
    输出：2
    解释：
    输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
    连续子数组里面拥有相同度的有如下所示：
    [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
    最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。
    示例 2：
    
    输入：nums = [1,2,2,3,1,4,2]
    输出：6
    解释：
    数组的度是 3 ，因为元素 2 重复出现 3 次。
    所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。
     
    
    提示：
    
    nums.length 在 1 到 50,000 范围内。
    nums[i] 是一个在 0 到 49,999 范围内的整数。
    */
    /**
     * 题目的意思有“数组的度”和“最短连续子数组”，概念理解起来较为复杂；<br/>
     * 转化下描述：找出出现次数最多的数字，标记起始位和结束位的最小值。 <br/>
     * 因为可能存在多个出现次数相同的数字，取(结束位-起始位+1)的最小值。<br/>
     * 描述2：找1个覆盖出现次数最多数字的子数组；如果最多数字有多个，找最短的子数组<br/>
     * 解法：遍历数字，统计每个数字出现的次数，维护起始位和结束位，最后比较大小
     * 
     * @param nums
     * @return
     */
    public int findShortestSubArray(int[] nums) {
        Map<Integer, NumCountIndex> numCountIndexMap = numCountIndexMap(nums);
        //1个数的最大次数（数组的度）
        int maxCount = 0;
        // 数组的度->最短连续子数组的长度
        Map<Integer,Integer> maxCountMinLengthMap=new HashMap<>();
        //遍历map，更新最大次数、最小长度和2者的map
        for (Map.Entry<Integer, NumCountIndex> entry : numCountIndexMap.entrySet()) {
            Integer count = entry.getValue().count;
            //最大的次数
            if (count >= maxCount) {
                maxCount = count;
                int maxCountMinLength = maxCountMinLength(maxCountMinLengthMap, entry, count);
                maxCountMinLengthMap.put(maxCount, maxCountMinLength);
            }
        }
        return maxCountMinLengthMap.get(maxCount);
    }

    private int maxCountMinLength(Map<Integer, Integer> maxCountMinLengthMap, Map.Entry<Integer, NumCountIndex> entry,
        Integer count) {
        //最小的长度
        int currentMinLength = entry.getValue().lastIndex - entry.getValue().firstIndex + 1;
        Integer length = maxCountMinLengthMap.get(count);
        int maxCountMinLength = 0;
        if(length==null) {
            maxCountMinLength=currentMinLength;
        }else {
            maxCountMinLength=Math.min(length, currentMinLength);
        }
        return maxCountMinLength;
    }

    /**
     * 根据数组构造map，维护数字、出现的次数、第1次的index、最后1次的index
     * @param nums
     * @return
     */
    private Map<Integer, NumCountIndex> numCountIndexMap(int[] nums) {
        Map<Integer, NumCountIndex> map = new HashMap<>();
        for (int index=0;index<nums.length;index++) {
            int num=nums[index];
            NumCountIndex numCountIndex = map.get(num);
            if(numCountIndex==null) {
                //第1次初始化
                numCountIndex = new NumCountIndex();
                numCountIndex.count=1;
                numCountIndex.firstIndex=index;
                //也需要初始化
                numCountIndex.lastIndex=index;
                //不关键，本题不需要，习惯性额外维护关键信息
                numCountIndex.num=num;
                map.put(num, numCountIndex);
            }else {
                numCountIndex.count++;
                numCountIndex.lastIndex=index;
            }
        }
        return map;
    }

    class NumCountIndex {
        int num;
        int count;
        int firstIndex;
        int lastIndex;
        @Override
        public String toString() {
            return "NumCountIndex [num=" + num + ", count=" + count + ", firstIndex=" + firstIndex + ", lastIndex="
                + lastIndex + "]";
        }
        
    }
}
